package mx.unam.ia.estructuras;

import java.util.LinkedList;
import mx.unam.ia.algoritmos.OperacionBinaria;
import mx.unam.ia.algoritmos.OperacionUnaria;
import mx.unam.ia.algoritmos.Terminal;

/**
 *
 * @author Juan Fco. Navarrete
 */

//Se obtiene la expresion del arbol binario dependiendo de su raiz y de su profundidad.
public class ArbolExpresionBinario
{
    private Nodo raiz;
    private int maxProfundidad;    

    public ArbolExpresionBinario(Nodo raiz) //Se define la raiz
    {
        this.raiz = raiz;
    }

    public Nodo getRaiz() //Se obtiene la raiz
    {
        return raiz;
    }

    public void setRaiz(Nodo raiz) //Se establece la raiz
    {
        this.raiz = raiz;
    }

    public int tamaño() //Se define el tamaño de la raiz
    {
        return(tamaño(raiz));
    }

    private int tamaño(Nodo nodo) //Se define el tamaño de los nodos del lado derecho, izquierdo y de la raiz.
    {
        if (nodo == null)
            return(0);        
        else        
            return(tamaño(nodo.getIzquierdo()) + 1 + tamaño(nodo.getDerecho()));        
    }

    public int profundidadMaxima() //Se establece la profunidad maxima,
    {
         maxProfundidad=profundidadMaxima(raiz);
        return maxProfundidad;
        
    }
     public int getMaxProfundidad() //Se obtiene el tamaño de la profundidad
    {
        return maxProfundidad;
    }

    private int profundidadMaxima(Nodo nodo) //Se obtiene el valor de la profundiad maxima, si no existen nodos el valor es cero, sino es asi
            //se obtiene el mayor valor entre la profundidad del lado derecho y del lado izquierdo y se le suma la raiz.
    {
        if (nodo==null)        
            return(0);
        else
        {
            int profundidadIzquierdo = profundidadMaxima(nodo.getIzquierdo());
            int profundidadDerecho = profundidadMaxima(nodo.getDerecho());            
            return(Math.max(profundidadIzquierdo, profundidadDerecho) + 1);
        }
    }

    public String enOrden() //Se ordena el recorrido desde la raiz
    {
        StringBuilder recorrido = new StringBuilder();
        enOrden(raiz, recorrido);
        return recorrido.toString();
    }

    private void enOrden(Nodo nodo, StringBuilder recorrido) //Se ordena el recorrido del lado izquierdo y derecho.
    {
        if (nodo == null)        
            return;        
        enOrden(nodo.getIzquierdo(), recorrido);
        recorrido.append(nodo.getDato() + " ");
        enOrden(nodo.getDerecho(), recorrido);
    }

    public String postOrden() //Se ordena el recorrido en "post orden"
    {
        StringBuilder recorrido = new StringBuilder();
        postOrden(raiz, recorrido);
        return recorrido.toString();
    }

    private void postOrden(Nodo nodo, StringBuilder recorrido) //El post orden obtiene los valores con el orden invertido
    {
        if (nodo == null)
            return;
        recorrido.append(nodo.getDato());
        postOrden(nodo.getIzquierdo(), recorrido);
        postOrden(nodo.getDerecho(), recorrido);
    }

    public LinkedList<String> recorridoPostOrden() //Se obtiene una lista del recorrido desde la raiz
    {
        LinkedList<String> recorrido = new LinkedList<String>();
        recorridoPostOrden(raiz, recorrido);
        return recorrido;
    }

    private void recorridoPostOrden(Nodo nodo, LinkedList<String> recorrido) //Se obtiene una lista del recorrido post orden
    {
        if (nodo == null)
            return;
        recorrido.add(nodo.getDato());
        recorridoPostOrden(nodo.getIzquierdo(), recorrido);
        recorridoPostOrden(nodo.getDerecho(), recorrido);
    }

   //Se va generando la expresion del arbol binario.
   //Con la expresion Karva: se obtiene el nodo raiz y sus nodos hijo y padre, el padre
    //buscara nodos libres y se les asignara un hijo ya sea del lado derecho o izquierdo
    public static ArbolExpresionBinario generar(String expresionKarva)
    {
        StringBuilder expresion = new StringBuilder(expresionKarva);
        Nodo raiz = new Nodo(Character.toString(expresion.charAt(0)));
        ArbolExpresionBinario arbolBinario = new ArbolExpresionBinario(raiz);
        for (int i = 1; i < expresion.length(); i++)
        {
            Nodo hijo = new Nodo(Character.toString(expresion.charAt(i)));
            Nodo padre = buscarNodoLibre(arbolBinario);
            if(padre == null)
                break;
            else if(padre.getIzquierdo() == null)
                padre.setIzquierdo(hijo);            
            else            
                padre.setDerecho(hijo);            
        }
        return arbolBinario;
    }

    //para buscar el nodo libre se deve de verificar los valores sean nulos tanto el izquierdo como el derecho
    private static Nodo buscarNodoLibre(ArbolExpresionBinario arbolBinario)
    {
        LinkedList<Nodo> cola = new LinkedList<Nodo>();
        cola.offer(arbolBinario.getRaiz());
        while(!cola.isEmpty())
        {
            Nodo nodo = cola.poll(); //remueve el primer elemento de la lista
            if(esNodoLibre(nodo))            
                return nodo;            
            else
            {
                if(nodo.getIzquierdo() != null)              
                    cola.offer(nodo.getIzquierdo());      //devuelve cierto elemento a la cola
                if(nodo.getDerecho() != null)                
                    cola.offer(nodo.getDerecho());                
            }
        }
        return null;
    }

   //Para verificar que es un nodo libre recibiendo como parametros los nodos, se coloca una
   //bandera, y se debe de verificarsi el nodo izquierdo y el derecho son nulos.
    private static boolean esNodoLibre(Nodo nodo)
    {
        boolean libre = false;
        String dato = nodo.getDato().toString();
        if(OperacionBinaria.esBinaria(dato))
            libre = (nodo.getIzquierdo() == null || nodo.getDerecho()== null) ? true : false;        
        else if(OperacionUnaria.esUnaria(dato))
            libre = (nodo.getIzquierdo() == null) ? true : false;        
        else        
            libre = false;        
        return libre;
    }   


   //Se evalua el recorrido en postorden y se verifica si es un terminal para que sea reemplazado..
    public double evaluar(double x, double r)
    {
        LinkedList<String> recorrido = recorridoPostOrden();
        int i = 0;
        for (String string : recorrido)
        {            
            if(Terminal.esTerminal(string))
            {                
                recorrido.set(i, Double.toString(Terminal.reemplaza(string, x, r)));
            }            
            i++;
        }
        return evaluar(recorrido);
    }

   //Al evaluar la lista del recorrido se repetirá el ciclo que verifica si la operacion es binaria
   // y ya sea que coloque los elementos sobre la pila o los remueva al aplicar la operacion.
   //Si la operacion es unaria realizara obtendra la respectiva evaluacion.
    private double evaluar(LinkedList<String> recorrido)
    {
        LinkedList<String> pila = new LinkedList<String>();        
        while(!recorrido.isEmpty())
        {            
            String simbolo = recorrido.removeLast();
            if(OperacionBinaria.esBinaria(simbolo))
            {
                double op1 = Double.parseDouble(pila.pop());
                double op2 = Double.parseDouble(pila.pop());                
                double resultado = OperacionBinaria.aplicar(simbolo, op1, op2);
                pila.push(Double.toString(resultado));
            }
            else if(OperacionUnaria.esUnaria(simbolo))
            {
                double op1 = Double.parseDouble(pila.pop());                
                double resultado = OperacionUnaria.aplicar(simbolo, op1);
                pila.push(Double.toString(resultado));
            }
            else            
                pila.push(simbolo);            
        }        
        return Double.parseDouble(pila.pop());
    }
}
